package com.wlr.study.leetcode;


/**
 * 路径总和
 * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
 * 输出：true
 *
 * @author lrwang
 * @version 1.0
 * @date 2022/4/7 15:09
 */
public class LeetCode112 {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null && targetSum == root.val) {
            return true;
        }
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }


    public static void main(String[] args) {
        TreeNode r0 = new TreeNode(5);
        TreeNode r1 = new TreeNode(4);
        TreeNode r2 = new TreeNode(11);
        TreeNode r3 = new TreeNode(7);
        TreeNode r4 = new TreeNode(2);
        TreeNode r5 = new TreeNode(8);
        TreeNode r6 = new TreeNode(13);
        TreeNode r7 = new TreeNode(4);
        TreeNode r8 = new TreeNode(1);
        r0.left = r1;
        r1.left = r2;
        r2.left = r3;
        r2.right = r4;
        r0.right = r5;
        r5.left = r6;
        r5.right = r7;
        r7.right = r8;
        LeetCode112 leetcode112 = new LeetCode112();
        System.out.println(leetcode112.hasPathSum(r0, 22));
        LeetCode113 leetcode113=new LeetCode113();
        System.out.println(leetcode113.pathSum(r0, 22));
    }

}
